package com.hr;

import java.util.Comparator;

/**
 * @program: leetcode
 * @description: 跳表
 * @author: HuRan QQ1345122890
 * @create: 2021-08-2 21:01
 */
public class SkipList<K, V> {
    private int size;
    private static final double P = 0.25;
    private Comparator<K> comparator;
    private static final int MAX_LEVEL = 32;
    private int level; //有效层
    //虚拟节点 不存放任何值
    private Node<K, V> first;

    public SkipList(Comparator<K> comparator) {
        this.comparator = comparator;
        first = new Node<>(null, null);
        first.nexts = new Node[MAX_LEVEL];
    }

    public SkipList() {
        this(null);
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public V put(K key, V value) {
        keyCheck(key);
        Node<K, V> node = first;
        //存储每一层的前驱
        Node<K, V>[] prevs = new Node[level];
        for (int i = level - 1; i > 0; i--) {
            int cmp = 0;
            //找节点
            while (node.nexts[i] != null && (cmp = compare(key, node.nexts[i].key)) > 0) {
                node = node.nexts[i];
            }
            if (cmp == 0) {
                //该元素存在 覆盖
                V oldV = node.nexts[i].value;
                node.nexts[i].value = value;
                return oldV;
            }
            prevs[i] = node;

            
        }
        //意味着 -已经确定前驱节点是 //添加新节点
        Node<K, V> newNode = new Node<>(key, value);
        final int newLevel = randomLevel();

        //确定层数
        size++;
        return null;
    }

    private int randomLevel() {
        int level = 1;
        while (Math.random() < P && level < 32) {
            level++;
        }

        return level;
    }

    public V get(K key) {
        keyCheck(key);
        Node<K, V> node = first;
        for (int i = level - 1; i > -0; i--) {
            int cmp = 0;
            //找节点
            while (node.nexts[i] != null && (cmp = compare(key, node.nexts[i].key)) > 0) {
                node = node.nexts[i];
            }
            if (cmp == 0) {
                return node.nexts[i].value;
            }
        }
        return null;
    }

    public V remove(K k) {
        return null;
    }

    private int compare(K k1, K k2) {
        return comparator != null ? comparator.compare(k1, k2) :
                ((Comparable<K>) k1).compareTo(k2);
    }

    private void keyCheck(K key) {
        if (key == null) {
            throw new IllegalArgumentException("kye must not be null");
        }
    }

    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V>[] nexts;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

}